Value memoization is an optimization process that may eliminate redundant calculations and/or memory operations in a computer program by caching the output results of previous executions of complex instructions, a group of instructions, software functions or subroutines, or even groups of software functions or subroutines. In cases where the memoization is successful, i.e., the sought results do exist in value cache, value memoization may drastically reduce computation time and electrical power consumption of a computing system by only performing a specific operation at a time i.e., the value lookup operation.
However, as it can be recognized by those skilled in the art, value memoization may add time and electrical power consumption overheads to a computer program and system. The overheads may include testing the value cache prior to executing a particular code segment plus the overheads of storing and retrieving the results. In other words, the potential benefits of memoization not only depend on the number of instances it has eliminated, but, inter alia, on the time and electrical power spent in detecting the instances to be eliminated.
An exemplary embodiment of the technology disclosed in this application targets to increase the paybacks, measured either in terms of electrical power savings, or as performance improvements, or both, from utilizing memoization techniques especially when approximate memoizations are performed, i.e., small and controllable errors are intentionally allowed to occur during the memoization process. The applicants believe that there remains scope for improvements to approximate memoization and similar operations in computing systems. Thereby, it is desirable to provide new methods and apparatus for facilitating further electrical power savings and performance improvements when approximate memoization techniques are employed.
There have been proposed several disclosed methods that utilizing the value memoization technique for performance improvements. For example US2013/0073837, US2013/0074057, US2011/0302371, and US2012/0096448, where the applicants apply the value reuse technique at the boundaries of the application source code functions and they try to optimize the performance payback by selecting the most appropriate functions to perform memorization and by memorizing and reusing the results of the most frequently requested input parameters.
Kamimura et al. (“A Speed-up Technique for an Auto-Memoization Processor by Reusing Partial Results of Instruction Regions,” 978-0-7695-4893-7/12, IEEE, 5-7 Dec. 2012) proposes a memorization technique wherein the detection and analysis of code segments for memoization is performed in the processor hardware.
U.S. Pat. No. 5,774,386 wherein the inventors break a color transformation function into subfunctions and the intermediate results of each subfunction are used for memorization. U.S. Pat. No. 6,553,394 wherein the invertors perform memoization using interpolation to generate results for input parameters that are near values of cached arguments. US2002/0152368 wherein the invertors propose a processor with instructions that include a value prediction field which is retained in a cache. U.S. Pat. No. 6,810,474 wherein the inventors propose a processor that caches instructions that have a long execution time along with their output values.
The inventors believe that the value memoization techniques in prior art differs from what is disclosed in this application in at least five reasons.
First, the applicants propose to extend the instruction set architecture (also known as an ISA) of the computing system intended to employ the technology disclosed in the present application with new instructions (also known as specifications) dedicated for the operation and the management of the value cache. The dedicated machine instructions may also embed an indication to manage approximations during the value memoization process.
Second, the applicants propose to extend the processing path (also known as data path) of the computing system intended to employ the technology disclosed in the present application with a new, special purpose functional unit dedicated to perform memoization. This special purpose functional unit may also employ additional functionality to reduce the precision of the input parameters during the process of matching the input parameters to the arguments stored in the special purpose functional unit, i.e., the value cache.
Third, the applicants disclose methods and techniques utilizing an electrical power minimization approach to identify appropriate points in the source or executable code of a software program and insert on those points the memoization management instructions.
Fourth, a hardware mechanism is disclosed which may monitor the dynamic behavior of an executing computer program and specific means are provided to deactivate and reactivate the memoization operations during the execution of the specific computer program.
Fifth, an additional mechanism is disclosed which may monitor the quality of the results generated by the approximate memoizations and specific means are provided to modify the precision of the input parameters during the process of matching the input parameters to the arguments stored in the value cache during the execution of one or more code segments of a particular computing program.
Sixth, the value cache storage area is augmented with extra functionalities, e.g., to dynamically change the order of the executing instructions of the executing computer program.